//串
#include <stdio.h>
#include <stdlib.h>
#define maxSize 100

//定长顺序存储结构—————给出最长的串长maxSize
typedef struct
{
	char str[maxSize+1];//maxSize表示最大串长————字符Str多个‘\0’的空间
	int length;//表示当前串长和定位串尾元素
}fixedLengthStr;


//变长分配存储结构————根据需要，改变串长
typedef struct
{
	char *ch; //字符指针，指向串首
	int length; //记录当前串长
}changeableLengthStr;


int main(int argc, char *argv[]) {
	//串的定义————定义一个串str
	char str[] = "abcdef"; //数组长度为 7 ；作为串，其串长为 6
	//串长————表示一个串里面元素的个数
	//空串————串里面没有元素。 空格串————串里面只含空格
	//子串————主串里面连续字符组成的 子序列
	
}


/*****串的基本操作*****/
//赋值操作————已知一个数组，将其元素赋值到串中
void StrAssign(changeableLengthStr *str,char *c)
{				//要进行赋值操作的串	//指向已有字符数组的指针
	
	if((*str).ch)
		free((*str).ch);//如果要操作的串，本身有元素，则将原本的元素释放掉
	
	char *ch = c;//创造一个辅助指针————用来遍历已有字符数组，求出其长度，方便以后的赋值操作————同时，保持*c指向字符数组的入口
	int len = 0;//用于记录原有字符数组的长度
	
	while(ch)//遍历原有数组————求出其长度
	{
		len++;
		ch++;
	}
	
	if(len==0)//如果原有数组里没有元素————赋值之后，返回空串
	{
		(*str).ch = NULL;
		(*str).length = 0;
		return;
	}
	
	else{//如果数组中有元素————为串开辟空间————开始赋值
		
				//将开辟空间的类型转变为char————多开辟的空间，存储其他char————效果：开辟了一个字符数组空间
		(*str).ch = (char *)malloc(sizeof(char)*(len+1));
		//存储数组首地址		//开辟空间，多开辟一个空间用来存储'\0'
		
		ch = c;//让辅助指针回归————保证c指针始终定位 原数组的头部
		
		for(int i=0;i<=len;i++,ch++)//‘=’号，将'\0'也赋值了进去
				(*str).ch[i] = *ch;
			//前面为指针开辟了一个字符数组空间，因此，该指针可当成数组使用
			
		(*str).length = len;
		return;
	}
}


//串的比较操作————前者更大，则返回 1 ； 后者更大，则返回 2 ; 相同，则返回 0
//————比较规则：比较两字符串首元素的ASCII码————若相同，则比较下一个元素————若元素的ASCII码都相同，则比较字符串长度
int strCompare(fixedLengthStr str1,fixedLengthStr str2)
{
	//比较元素的ASCII码
	for(int i=0;i<str1.length&&i<str2.length;i++)
	{
		if(str1.str[i] > str2.str[i])return 1;
		else if(str1.str[i] < str2.str[i])return 2;
	}
	//ASCII码无法得出结论————比较长度
	if(str1.length > str2.length)return 1;
	else if(str1.length > str2.length)return 2;
	//上面两次均无法得出结论————两串相等
	else return 0;
}


//串的连接————将str1、str2首尾相连，用str储存
void concatenate(changeableLengthStr *str,changeableLengthStr str1,changeableLengthStr str2)
{
	if(str->ch)//先让str为空，去除其原有的元素
	{
		free(str->ch);//释放空间，避免空间的浪费
		str->ch = NULL;//再指向NULL
	}
	
	str->ch = (char *)malloc(sizeof(char)*(str1.length+str2.length+1));//开辟一个存储字符数组的空间
	int i = 0;
	for(;i<str1.length;i++)//将str1中的元素赋值给str
		str->ch[i] = str1.ch[i];
	for(int j=0;i<=str1.length+str2.length;i++,j++)//将str2中的元素,包括最后的'\0'赋值给str
		str->ch[i] = str2.ch[i];
	
	str->length = i-2;//变化str的长度
}


//求取子串subStr————从主串str的start位置开始，向后取len个元素，作为子串————取成功，返回 1；取失败，返回 0
int getSubString(changeableLengthStr *subStr,changeableLengthStr str,int start,int len)
{
	if(start<0||start>str.length||len<0||len>str.length-start)//非法取子串——返回 0
		return 0;
	
	//先删除subStr原有元素
	if(subStr->ch)
	{
		free(subStr->ch);
		subStr->ch = NULL;
	}
	
	if(len == 0)//长度为 0————返回空子串
	{
		subStr->ch = NULL;
		subStr->length = 0;
		return 1;
	}
	else {
		subStr->ch = (char *)malloc(sizeof(char)*(len+1));//开辟空间
		for(int i=0,j=start;i<len;i++,j++)//进行赋值
			subStr->ch[i] = str.ch[j];
		
		subStr->ch[len] = '\0';
		subStr->length = len;
		return 1;
	}
	return 0;
}


//串的模式匹配————给定一个子串（模式串），找到该子串在主串中的位置，已知子串长len————只需要找到开始位置start即可
				//————若该子串不在该主串中，则返回 0； 若是，则返回 start
int index(changeableLengthStr subStr,changeableLengthStr str)
{
	int start = 0;//定位开始位置
	int i = 0;//用于遍历主串
	int j = 0;//用于遍历子串
	while(i<=str.length&&j<=subStr.length)
	{					//遍历之后，发现子串各元素均匹配之时，跳出循环
		if(str.ch[i]==subStr.ch[j])//开始遍历，元素匹配之时，继续遍历下一个元素————若遍历完子串时，则可以确定子串的位置
		{
			i++;
			j++;
		}
		else{//元素未匹配之时，从头遍历子串，从主串start的下一位开始遍历
			i = ++start;//定位到主串的下一个元素，再次尝试遍历
			j = 0;
		}
	}
	if(j>subStr.length)//如果是第一种结果
		return start;
	else return 0;//如果遍历完主串，还没有发现匹配该子串的，则匹配失败
}

/*KMP算法*/